<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<html><head>
<!--Converted with LaTeX2HTML 98.1 release (February 19th, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
  Jens Lippmann, Marek Rouchal, Martin Wilck and others -->


<title>Compromise</title>
<meta name="description" content="Compromise">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<link rel="STYLESHEET" href="acm-00531_archivos/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">

<h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font color="#c0ffff" size="5">&nbsp;<a name="SECTION0001000000000000000000">
Compromise</a>&nbsp;</font></b></td></tr></tbody></table></center>
</h1>

<p>
In a few months the European Currency Union will become a reality. However, to
join the club, the
Maastricht criteria must be fulfilled, and this is not a trivial task for the
countries (maybe except for
Luxembourg). To enforce that Germany will fulfill the criteria, our government
has so many
wonderful options (raise taxes, sell stocks, revalue the gold reserves,...)
that it is really hard to
choose what to do.

</p><p>

</p><p>
<br>
Therefore the German government requires a program for the following task:

</p><p>

</p><p>
<br>
Two politicians each enter their proposal of what to do. The computer
then outputs the longest
common subsequence of words that occurs in both proposals. As you can see,
this is a totally fair
compromise (after all, a common sequence of words is something what both
people have in mind).

</p><p>

</p><p>
<br>
Your country needs this program, so your job is to write it for us.

</p><p>

</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">
Input Specification</a>&nbsp;</font>
</h2>
The input file will contain several test cases.

<p>
Each test case consists of two texts. Each text is given as a sequence of
lower-case words, separated
by whitespace, but with no punctuation. Words will be less than 30 characters
long. Both texts will
contain less than 100 words and will be terminated by a line containing a
single '<tt>#</tt>'.

</p><p>
Input is terminated by end of file.

</p><p>

</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">
Output Specification</a>&nbsp;</font>
</h2>
For each test case, print the longest common subsequence of words occuring
in the two texts. If
there is more than one such sequence, any one is acceptable. Separate the
words by one blank. After the last word, output a newline character.

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">
Sample Input</a>&nbsp;</font>
</h2>
<pre>die einkommen der landwirte
sind fuer die abgeordneten ein buch mit sieben siegeln
um dem abzuhelfen
muessen dringend alle subventionsgesetze verbessert werden
#
die steuern auf vermoegen und einkommen
sollten nach meinung der abgeordneten
nachdruecklich erhoben werden
dazu muessen die kontrollbefugnisse der finanzbehoerden
dringend verbessert werden
#
</pre>

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">
Sample Output</a>&nbsp;</font>
</h2>
<pre>die einkommen der abgeordneten muessen dringend verbessert werden
</pre>

<p>

</p><p>
</p></body></html>